package com.LeeCode;

/**
 * 从叶结点开始的最小字符串
 */

public class Code988 {
    public static void main(String[] args) {
        Integer[] arr = {0, 1, 2, 3, 4, 3, 4};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code988().smallestFromLeaf(root));

    }


    String ans = null;

    public String smallestFromLeaf(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();

        dfs(root, stringBuilder);
        return ans;
    }

    private void dfs(TreeNode root, StringBuilder stringBuilder) {
        if (root == null) return;

        stringBuilder.insert(0, (char) (root.val + 'a'));

        if (root.left == null && root.right == null) {
            String str = stringBuilder.toString();
            if (ans == null || ans.compareTo(str) > 0) {
                ans = str;
            }
        }

        dfs(root.left, stringBuilder);
        dfs(root.right, stringBuilder);
        stringBuilder.deleteCharAt(0);
    }
}
